/*
 * searchNode.cpp
 *
 *  Created on: Sep 18, 2011
 *      Author: ewertz
 */

#include "puzzleSettings.h"
#include "board.cpp"
using namespace std;

static pos rankOf(pos);

class node {
public:
	puzzle board;
	node * parent;//ONLY FOR PATH IN SEARCH

	node * next; //ONLY FOR nodeBroker linked list
	node * prev; //ONLY FOR nodeBroker linked list

	////// INSERT POINTERS FOR CUSTOM HEAP ALGORITHM

	unsigned char prevDirection; //the direction the blank was moves to create this state (used for pruning 2-cycles before generating nodes).
	unsigned char references;  //keeping track of number of nodes referring to this node.  starts at 0, if it hits 0, node is recycled.
	unsigned short cost_moves;  //number of moves so far
	unsigned short minDist;     //minimum moves to get to goal state.
	unsigned int cost;          //current cost of node;
	unsigned int hash;          //hash is cost - cost_moves;


	//constructor
	node(){
		//boards are generated in the "getChildren" function in response to the board generating possible moves.
		references = 0;
	}


	//destructor
	~node(){
		//no memory allocated by constructor that needs to be freed in destructor.
	}



	//display path to current node from initial config
	void displayPath(){
		if(parent != NULL){
			parent->displayPath();  //recurses to beginning of path.

		} else {
			//cout << "Initial Board Configuration: " << endl << endl;
		}
		cout << "move = " << cost_moves << "   cost = " << cost << "   hash = " << hash << endl;
		board.printBoard();
		cout << endl; //space gap after end of board.
	}

	void printNode(){

		if(debugAllNodes){
			int cost3 = minDist*coeff3;
			int cost2 = tilesOut()*coeff2;
			int cost4 = coeff4 * rankDistance();
			int cost5 = coeff5 * adjacentRank();
			int costSum = cost2 + cost3 + cost4;
			int cost1 = cost - costSum;
			cout << "hash = " << hash << endl;
			cout << "number of moves = " << cost_moves << endl;
			cout << "cost = " << cost  << " moves = "<< cost1 << " tiles out of place = "<< cost2 << " minDistance = "<< cost3 << " rankDistance = " << cost4 << " adjacentRank = " << cost5  << endl;
		}

		board.printBoard();

	}

	void load(node & active, int direction){
		board.load(active.board, direction);
		CostForChild(&active);
	}



	void CostForChild(node * active){

		minDist = minDistance();

		if(!calcHash){ //using custom

			hash =  coeff2*tilesOut()
					+ coeff3*minDist
					+ coeff4*rankDistance()
					+ coeff5*adjacentRank();

			if(active == NULL){ //root node
				cost_moves = 0;
				cost = coeff1 * cost_moves + hash;
			} else {
				cost_moves = active->cost_moves+1;
				cost = coeff1 * cost_moves + hash;
			}
		} else {

			if(active == NULL){ //root node
				cost_moves = 1;
				cost = coeff1 * cost_moves
						+ coeff2*tilesOut()
						+ coeff3*minDist
						+ coeff4*rankDistance()
						+ coeff5*adjacentRank();

			} else {
				cost_moves = active->cost_moves+1;
				cost = coeff1 * cost_moves
						+ coeff2*tilesOut()
						+ coeff3*minDist
						+ coeff4*rankDistance()
						+ coeff5*adjacentRank();
			}
			hash = 0;
			int modulus = sizeof(unsigned int)/(sizeof(pos));
			for(int i = 0; i < size; i ++){
				int factor = 1;
				int offset = (i % modulus);
				for(int j = 0; j < offset; j++)
					factor  = factor * 256;
				hash += board.board[i]*factor;
			}
		}



	}

	bool isGoal(){
		for(int i = 0; i < size; i++){
			if (board.board[i] == i){

			}
			else{
				return false;
			}
		}
		return true;
	}



	/*
	 * NOTE: Checking for immediate cycle is performed in the isValidMove function.
	 * Checking for cycles need only occur when
	 * 12 move cycle.
	 * 30
	 * 40
	 * 56 move cycles.
	 *
	 */
	bool checkForCycles(){

		node * temp = (this);
		int counter = 0;

		while(true){
			if(advancedCycleCheck){
				counter ++;  //how far back the ancestry we are.
				temp = temp ->parent;
				if (temp == NULL)
					break;
				switch(counter){
				case 12:
				case 30:
				case 40:
				case 56:
					if(isNodeSame(*this,*temp))  //comparing child to its ancestor.
						return true;
					break;
				default:
					if(counter %2 == 0) //check ancestors at frequency of even numbers.
						if(isNodeSame(*this,*temp)){  //comparing child to its ancestor.
						return true;
						}
					break;
				}
			} else {
				temp = temp ->parent;
				if (temp == NULL)
					break;
				if(debugAllNodes)
					temp->printNode();
				if(isNodeSame(*this,*temp)) //comparing child to its ancestor.
					return true;
			}
		}
		return false;


	}


	/*
	 * minDistance()
	 *
	 *  This determines the minimal distance of the board from the solution in terms of tile displacement
	 *  from their correct position.
	 *
	 *  Trow = row tile is supposed to be on
	 *  Tcol = col tile is supposed to be on.
	 *  Prow = row tile is currently placed on.
	 *  Pcol = col tile is currently placed on.
	 *
	 *  Displacement = Abs(Trow-Prow) + Abs(Tcol -Pcol)
	 *
	 *  Do this for each tile
	 */
	int minDistance(){
		int sum=0,val=0;
		for(int i=0;i<size;i++){
			val = board.board[i];  //this is the value of the tile, what position it is supposed to be in.
			pos Trow = val / width;  //row tile should be on
			pos Tcol = val % width; //col tile should be on
			pos Prow = i / width;   //row tile is on now
			pos Pcol = i % width;   //col tile is on now

			pos vertDist = 0;
			pos horzDist = 0;
			if(Tcol < Pcol) //get positive horizontal distance
				horzDist = Pcol-Tcol;
			else
				horzDist = Tcol-Pcol;
			if(Trow < Prow) //get positive vertical distance
				vertDist = Prow - Trow;
			else
				vertDist = Trow - Prow;

			sum += (vertDist + horzDist); //add the distances to the sum.

		}
		return sum;
	}

/*
 *  rankDistance ()
 *
 *  This takes the distance function and weights the tile's distance based on their rank. (see rank function)
 *
 *
 *  Trow = row tile is supposed to be on
 *  Tcol = col tile is supposed to be on.
 *  Prow = row tile is currently placed on.
 *  Pcol = col tile is currently placed on.
 *
 *  ranked Displacement = rank *( Abs(Trow-Prow) + Abs(Tcol -Pcol) )
 *
 *  Do this for each tile and sum together.
 */
int rankDistance(){
	int sum=0,val=0;
	for(int i=0;i<size;i++){
		val = board.board[i];  //this is the value of the tile, what position it is supposed to be in.
		pos Trow = val / width;  //row tile should be on
		pos Tcol = val % width; //col tile should be on
		pos Prow = i / width;   //row tile is on now
		pos Pcol = i % width;   //col tile is on now

		pos vertDist = 0;
		pos horzDist = 0;
		if(Tcol < Pcol) //get positive horizontal distance
			horzDist = Pcol-Tcol;
		else
			horzDist = Tcol-Pcol;
		if(Trow < Prow) //get positive vertical distance
			vertDist = Prow - Trow;
		else
			vertDist = Trow - Prow;

		sum += rankOf(val)*(vertDist + horzDist); //add the distances to the sum.

	}
	return sum;
}

/*
 * This simply counts the number of tiles that are not in their proper position.
 */
int tilesOut(){
	if(coeff2 > 0){
	int sum=0;
		for(int i=0;i<size;i++){
			if(board.board[i]!=i)
				sum = sum +1;

		}
		return sum;
	}
	return 0;

}

/*
 * returns the number of tiles not adjacent to their left neighbor weighted by their rank.
 *
 * for each tile, if tile to the left is up, left, down or right, cost = 0, else rank.   If on edge left, no cost.  Checks outer most rank if in place, no cost.
 *
 *
 */
int adjacentRank(){
	if(coeff5 > 0){
	//first find the rank that is not complete
	pos highestRank = rankOf(size-1);
	cout << "highestRank  = " << highestRank << endl;
	bool complete = true;
	while(complete && highestRank > 0){
		pos row = highestRank * width;
		for(pos col = 0; col< width; col++){
			pos index = row + col;
			if(board.board[index] != index)
				complete = false;
		}
		pos col = width-1;
		for(pos index = col+row; index > 0; index -= width)
			if(board.board[index] != index)
				complete = false;
		if(complete == false)
			continue;
		highestRank--;
	}

	//this should be the rank that is incomplete.
	int cost = 0;
	for(pos row = 0; row <= highestRank; row ++){
		for(pos col = 0; col <= highestRank; col ++){
			pos index = row * width + col;
			pos value = board.board[index];
			if(value % width == 0) //on the 0th column, no left neighbor
				continue; //skip element.
			//else look for neighbor to left.
			pos neighbor = value -1;
			pos up = index - width;
			pos down = index + width;
			pos left = index -1;
			pos right = index + 1;
			if(row != 0) //up exists
				if(board.board[up] == neighbor)
					continue; //no cost;
			if(col != 0) //left exists
				if(board.board[left] == neighbor)
					continue; //no cost;
			if(col < width-1) //right exists
				if(board.board[right] == neighbor)
					continue; //no cost;
			if(row < width -1) //down exists
				if(board.board[down] == neighbor)
					continue; //no cost
			//else cost adds rank of the node.
			cost += rankOf(value);
		}
	}
	return cost;
	}
	return 0;
}



/*
 * This weights the rows and column positions being completed further from the 0 point.
 *
 * CODE IS COMMENTED OUT BECAUSE TESTING HAS SHOWN NO EFFECT
 *
 *
int rankRowAndCol(){
	int cost = 0;
	bool complete = true;
	for(int rank = width -1; rank >= 0; rank--){
		pos col;
		if(complete)
			for(col = 0; col <= rank; col++){
				pos index = rank * width + col;
				if(board.board[index] !=  index){
					complete = false;
					break;
				}
			}
		if(complete)
			for(int row = rank; row >= 0; row--){
				pos index = row * width + col;
				if(board.board[index] != index){
					complete = false;
					break;
				}
			}
		if(!complete){
			cost += rank;
		}
	}
	return cost;

}

*/

bool isNodeSame(node & n1, node & n2){

	if((n1.hash)!= (n2.hash))
		return false;

	for(int i=0; i<size;i++){
		if(n1.board.board[i] !=  n2.board.board[i]){
			return false;
		}
	}
	return true;
}

};


/*
 * rankOF tile
 *
 * returns the max of the proper column or row position as the rank of the tile.
 * NOTE: nxn boards with completed outer ranks become a case of completing (n-1)x(n-1) puzzles.
 */
static pos rankOf(pos tile){
	if(!rankingOn)
		return 1;  // no scaling based on rank.
	pos row = tile/width;
	pos col = tile%width;
	if(row > col)
		return row;
	else
		return col;
}





